package com.zjsru.leetcode75.level1.chian;

/**
 * @Author: cookLee
 * @Date: 2023-12-10
 * 链表最大孪生和
 * 在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
 */
public class PairSum {

    /**
     * 主
     * \
     * 输入：head = [5,4,2,1]
     * 输出：6
     * 解释：
     * 节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
     * 链表中没有其他孪生节点。
     * 所以，链表的最大孪生和是 6 。
     * \
     * 输入：head = [4,2,2,3]
     * 输出：7
     * 解释：
     * 链表中的孪生节点为：
     * - 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
     * - 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
     * 所以，最大孪生和为 max(7, 4) = 7 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(2, new ListNode(3))));
        PairSum pairSum = new PairSum();
        System.out.println(pairSum.pairSum(head));
    }

    public int pairSum(ListNode head) {
        //pre 反转-链表的前半部分。 4-2-2-3 => pre:2-4
        ListNode pre = null;
        //慢指针，每次向前移动一步。
        ListNode p1 = head;
        //快指针，每次向前移动两步。
        ListNode p2 = head;
        while(p2 != null){
            p2 = p2.next.next;
            ListNode temp = p1.next;
            p1.next = pre;
            pre = p1;
            p1 = temp;
        }
        int max = 0;
        while(pre != null){
            max = Math.max(max, pre.val + p1.val);
            pre = pre.next;
            p1 = p1.next;
        }
        return max;
    }

}
